class Solution {
public:
    unordered_map<int, int> m;
    TreeNode* dfs(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir)
    {
        if(pl == pr) return NULL;

        int val = preorder[pl];
        auto root = new TreeNode(val);

        if(pr == pl + 1) return root;

        int k = m[val];

        root->left = dfs(preorder, pl + 1, pl + 1 + k - il, inorder, il, k);
        root->right = dfs(preorder, pl + 1 + k - il, pr, inorder, k + 1, ir);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++) m[inorder[i]] = i;
        return dfs(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};